package com.sicheng.蓝桥.练习题.dp.状态压缩;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/6 21:40
 */
public class 蒙德里安的梦想 {
    /**
     * 求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。
     * <p>
     * 例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。
     * <p>
     * 输入格式
     * 输入包含多组测试用例。
     * <p>
     * 每组测试用例占一行，包含两个整数 N 和 M。
     * <p>
     * 当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。
     * <p>
     * 输出格式
     * 每个测试用例输出一个结果，每个结果占一行。
     * <p>
     * 数据范围
     * 1≤N,M≤11
     * 输入样例：
     * 1 2
     * 1 3
     * 1 4
     * 2 2
     * 2 3
     * 2 4
     * 2 11
     * 4 11
     * 0 0
     * 输出样例：
     * 1
     * 0
     * 1
     * 2
     * 3
     * 5
     * 144
     * 51205
     */

    static boolean[] st;
    static long[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        int m;
        while ((n = sc.nextInt()) != 0 && (m = sc.nextInt()) != 0) {
            //dp[i][j] 第i列 状态为j的方式
            //j是压缩状态，二进制数
            // 1001 表示横 空 空 横
            // dp[i-1][k]转移到dp[i][j]  i-1扩展而来
            dp = new long[12][1 << n];
            st = new boolean[1 << n];
            dp[0][0] = 1;
            // 预存从i-1到i是否合法
            // i中连续0的个数不能是奇数
            for (int i = 0; i < 1 << n; i++) {
                //连续0的个数
                int count = 0;
                st[i] = true;
                for (int j = 0; j < n; j++) {
                    if (((i >> j) & 1) == 1) {
                        if ((count & 1) == 1) {
                            st[i] = false;
                            break;
                        }
                        count = 0;
                    } else
                        count++;
                }
                //处理高位为0
                if ((count & 1) == 1)
                    st[i] = false;
            }

            //枚举列
            for (int i = 1; i <= m; i++) {
                //i-1的状态
                for (int j = 0; j < 1 << n; j++) {
                    //i的状态
                    for (int k = 0; k < 1 << n; k++) {
                        //从i-1状态转移到i状态的条件
                        //1 横着的不可以冲突
                        //2 转移过来之后连续的0不可以为奇数
                        if ((j & k) == 0 && st[j | k])
                            dp[i][j] += dp[i - 1][k];
                    }
                }
            }
            System.out.println(dp[m][0]);
        }

    }
}
